#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/20 17:20
# ===========================================
#       题目名称： 60. 排列序列
#       题目地址： https://leetcode.cn/problems/permutation-sequence/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
import time
import itertools as _it


class Solution:

    def getPermutation(self, n: int, k: int) -> str:
        """
            思路 ， 找出最大位数的可能性 ， 然后找 k 的最大位数是啥 然后进行处理
        """
        s = time.time()
        const_values = [i for i in range(1, n + 1)]  # 常量
        cur_all_possibilities = []  # 当前所有的可能性
        while n > 0:
            if not cur_all_possibilities:
                cur_all_possibilities = [[val, ] for val in const_values]
            temp_cur_all_possibilities = []
            cur_all_possibilities.sort()

            for cur_possibilities in cur_all_possibilities:
                # 找出 cur_possibilities 和 const_values 的差集
                temp_const_values = [x for x in const_values.copy() if x not in cur_possibilities]
                for item in temp_const_values:
                    cur_items = cur_possibilities.copy()
                    cur_items.append(item)
                    temp_cur_all_possibilities.append(cur_items)
                if n == 0:
                    level = k % len(temp_cur_all_possibilities)

            if temp_cur_all_possibilities:
                cur_all_possibilities = temp_cur_all_possibilities
            print("n => %s,  k=> %s, len is => %s time: %s" % (n, k, len(cur_all_possibilities), time.time() - s))
            n -= 1
        cur_all_possibilities.sort()
        return "".join([str(item) for item in cur_all_possibilities[k - 1]])

    def getPermutation6(self, n: int, k: int) -> str:
        """
            时间超限
        """
        s = time.time()
        const_values = [i for i in range(1, n + 1)]  # 常量
        all_possibilities = {}  # 所有可能性
        while n > 0:
            if not all_possibilities:
                for i in range(len(const_values)):
                    tmp_const_values = const_values.copy()
                    del tmp_const_values[i]
                    all_possibilities[(const_values[i],)] = tmp_const_values
            tmp_all_possibilities = {}
            for key, value in all_possibilities.items():
                if not value:
                    continue
                for i in range(len(value)):
                    tmp_v = value.copy()
                    del tmp_v[i]
                    tmp_all_possibilities[key + (value[i],)] = tmp_v
            if tmp_all_possibilities:
                all_possibilities = tmp_all_possibilities
            n -= 1
            print("n => %s,  k=> %s, time: %s" % (n, k, time.time() - s))
        res = list(all_possibilities.keys())
        res.sort()

        return "".join((str(item) for item in res[k - 1]))

    def getPermutation5(self, n: int, k: int) -> str:
        """
            效率不行
        """
        s = time.time()
        # 定义返回值
        res = sum([i * pow(10, n - i) for i in range(1, n + 1)])
        # 定义常量列表
        const_list = [str(i) for i in range(1, n + 1)]
        # 保存
        save = []
        for item in _it.permutations(const_list, n):
            if set(item) == set(str(res)):
                save.append(int("".join(item)))
        save.sort()
        res = save[k - 1]
        print("n => %s,  k=> %s, time: %s" % (n, k, time.time() - s))
        return str(res)

    def getPermutation4(self, n: int, k: int) -> str:
        """
            批量生成数据 ， 将 符合规则的数据进行统计下来
            1、生成的N位数 每个数都不能是相同的
            时间超限
        """
        s = time.time()
        if not 1 <= n <= 9:
            return ""
        AREA = pow(10, n)
        MIN_VALUE = sum([i * pow(10, n - i) for i in range(1, n + 1)])
        MAX_VALUE = sum([i * pow(10, i - 1) for i in range(1, n + 1)])
        left, right = MIN_VALUE, MAX_VALUE if MAX_VALUE < AREA else AREA
        res = MIN_VALUE
        k -= 1
        while left <= MAX_VALUE and k > 0:
            for i in range(left + 1, right):
                # print(k , i)
                if set(str(i)) == set(str(res)):
                    # print(i)
                    k -= 1
                    res = i
                if k < 1:
                    break
            if k > 0:
                left = MAX_VALUE
                right = left + AREA
        print("n => %s,  k=> %s, time: %s" % (n, k, time.time() - s))
        return str(res)

    def getPermutation3(self, n: int, k: int) -> str:
        """
            批量生成数据 ， 将 符合规则的数据进行统计下来
            1、生成的N位数 每个数都不能是相同的
            时间超限
        """

        if not 1 <= n <= 9:
            return ""
        MIN_VALUE = sum([i * pow(10, n - i) for i in range(1, n + 1)])
        MAX_VALUE = sum([i * pow(10, i - 1) for i in range(1, n + 1)])
        res = MIN_VALUE
        COMPARE_LIST = list(str(MIN_VALUE))
        # 生成 MIN_VALUE 和 MAX_VALUE区间的数值
        s = time.time()
        while k - 1 > 0 and res <= MAX_VALUE:
            res += 1
            if sorted(str(res)) == COMPARE_LIST:
                if k - 1 == 0:
                    break
                k -= 1
        print("n => %s,  k=> %s, time: %s" % (n, k, time.time() - s))
        return str(res)

    def getPermutation2(self, n: int, k: int) -> str:
        """
            时间超限
        """
        elements = {str(i) for i in range(1, n + 1)}
        cur_level = 0
        while cur_level < n - 1:
            temp_elements = set()
            for element in elements:
                for i in range(1, n + 1):
                    if str(i) not in element:
                        temp_element = element + str(i)
                        temp_elements.add(temp_element)
            elements = temp_elements
            cur_level += 1
        elements = sorted(elements, key=lambda x: x)
        return elements[k - 1]


if __name__ == '__main__':
    s = Solution()
    # "213"
    print(s.getPermutation(n=3, k=3))
    # "2314"
    print(s.getPermutation(n=4, k=9))
    # "123"
    print(s.getPermutation(n=3, k=1))
    # "126847395"
    print(s.getPermutation(n=9, k=2678))
    # "972561438"
    print(s.getPermutation(n=9, k=353955))
    # "64158273"
    print(s.getPermutation(n=8, k=27428))
